package org.example;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[][] grid = new int[N + 1][N + 1];
        for (int[] row : grid) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            grid[u][v] = grid[v][u] = w;
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (grid[i][k] < Integer.MAX_VALUE && grid[k][j] < Integer.MAX_VALUE) {
                        grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);
                    }
                }
            }
        }

        int Q = sc.nextInt();
        for (int i = 0; i < Q; i++) {
            int st = sc.nextInt();
            int ed = sc.nextInt();
            int cost = grid[st][ed];
            if (cost < Integer.MAX_VALUE) {
                System.out.println(cost);
            } else {
                System.out.println(-1);
            }
        }
    }
}